The present invention pertains to the field of wireless communication technology. More specifically, the present invention pertains to decoding signals received by a receiver in a wireless communication system.
Wireless telephony has become a widely available mode of communication in modem society. Variable rate communication systems, such as Code Division Multiple Access (CDMA) spread spectrum systems, are among the most commonly deployed wireless technology. Variable rate communication systems transmit data in units called data frames.
CDMA utilizes digital encoding for every telephone call or data transmission in order to provide privacy and security. Unique codes are assigned to every communication, which distinguish it from the multitude of calls simultaneously transmitted over the same broadcast spectrum. Users share time and frequency allocations and are channelized by unique assigned codes. The signals are separated at the receiver in a known manner so that the receiver accepts only signals from the desired channel.
Some CDMA spread spectrum systems use a form of direct sequence in which, in essence, a communication waveform is modified by a pseudonoise binary sequence in the transmitter. A second modification by a replica of the pseudonoise binary sequence occurs in the receiver to recover the original signal. Generally, within a CDMA environment with a large number of users on the system, a high level of channel noise is usually present. In particular, each user is a source of noise to every other user on the same system. Undesired signals also contribute to the noise. Noise and interference, being uncorrelated with the pseudonoise binary sequence, add an element to the signal that needs to be considered when recovering the original signal.
Convolutional codes are known in the art and are used by the transmitter to encode a stream of binary digits. Typically, a convolutional encoder consists of a N-stage shift register and modulo-2 adders. Each digit of the digit stream is input into the shift register, and the convolutional code generates output digits that are an encoded version of the each input digit. For example, if the coding rate is 1/2, two output digits are generated for each input digit. A convolutional code is often represented in a known fashion using a trellis that shows the coded output for any possible sequence of input digits.
At the receiver, various techniques are known in the art for decoding a digital stream encoded using convolutional codes. The coding polynomial used in the convolutional code utilized by the transmitter is specified for the receiver, and so the receiver is able to decode the transmitted signal to determine expected values. However, due to the introduction of noise and interference during transmission, the received signal is likely to be different from the transmitted signal. A Viterbi decoder provides a well-known method to correct for errors introduced by noise and interference to determine decoded values based on the received signal. In essence, a Viterbi decoder determines the path through the convolutional code trellis that results in the sequence of digits that agrees most with the received sequence.
In the prior art, the expected values are calculated beforehand using the specified convolutional code and stored as a lookup table in, for example, a read-only memory (ROM). However, a disadvantage to the prior art is that the ROM occupies valuable physical space inside the receiver. Consumer preferences are for receivers to be as small and light as possible, and the need for ROM is contrary to these preferences.
Also, retrieving a value from ROM consumes battery power, and so larger and heavier batteries are required; otherwise, more frequent charging of the batteries is needed. However, this is also contrary to consumer preferences for smaller and lighter receivers, and it is also problematic because it likely increases the cost of the receiver.
In addition, retrieving a value from ROM consumes processing power, and so larger and more complex processors are required if a performance level acceptable to consumers is to be maintained. However, such processors are typically also more expensive, again contrary to consumer preferences for less costly receivers.
Accordingly, what is needed is an apparatus that cheaply and efficiently implements a technique for decoding a digital stream encoded using convolutional codes. What is also needed is an apparatus that addresses the above need and minimizes consumption of space, processing power, and battery power in a receiver. The present invention provides a novel solution to the above needs.
These and other objects and advantages of the present invention will become obvious to those of ordinary skill in the art after having read the following detailed description of the preferred embodiments which are illustrated in the various drawing figures.
The present invention provides an apparatus and method thereof that cheaply and efficiently implement a technique for decoding a digital stream encoded using convolutional codes. The present invention also provides an apparatus and method thereof that address the above need and minimize consumption of space, processing power, and battery power in a receiver.
The present embodiment of the present invention pertains to an apparatus and method thereof for decoding a stream of binary digits encoded according to a convolutional code. In a preferred embodiment, the apparatus is disposed within a receiver used in a communication system, in particular a communication system that uses code division multiple access (CDMA) spread spectrum type communication signals.
In the present embodiment of the present invention, the apparatus includes a bus, a N-bit counter coupled to the bus, and a trellis code generator coupled to the bit counter. The N-bit counter is adapted to generate a sequence of N binary bits (e.g., an initial state count). The trellis code generator includes a first logical gate and a second logical gate. The trellis code generator is adapted to specify a first set of binary digits from the sequence of N binary bits and to pass the first set of binary digits through the first logical gate to produce a first binary value. The trellis code generator is also adapted to specify a second set of binary digits from the sequence of N bits and to pass the second set of binary digits through the second logical gate to produce a second binary value. The first set of binary digits are particularly selected so that the first binary value emulates a first value of a first encoded bit that would have been determined using the convolutional code. Similarly, the second set of binary digits is selected so that the second binary value emulates a first value of a second encoded bit that would have been determined using the convolutional code. Thus, the apparatus is used to efficiently generate a trellis representing the convolutional code using logical gates.
In the present embodiment, the trellis code generator further comprises a first inverter for inverting the first binary value to produce a third binary value, and a second inverter adapted to invert the second binary value to produce a fourth binary value, wherein the third binary value emulates a second value of the first encoded bit that would have been determined using the convolutional code and the fourth binary value emulates a second value of the second encoded bit that would have been determined using the convolutional code.
In one embodiment, the trellis code generator is adapted to manipulate the sequence of N binary digits to generate a modified state count. The modified state count is used to generate the trellis representing the convolutional code.
In one embodiment, the apparatus includes a Viterbi decoder adapted to compute metrics by comparing the first binary value and the second binary value to the first encoded bit and the second encoded bit. The Viterbi decoder is further adapted to perform a traceback operation.
In this embodiment, the Viterbi decoder includes a first memory register for storing the metrics. An address in the first memory register is generated using the modified state count from the trellis code generator. The Viterbi decoder also comprises a second memory register for storing information for the traceback operation. An address in the second memory register is also generated using the modified state count trellis code generator. Thus, in accordance with the present embodiment of the present invention, the modified state count is used for generating a trellis representing a convolutional code, for addressing metric memory, and for addressing traceback memory.